package org.usmile.algorithms.learn.string;

public class RK {
    public int indexOf(String mainStr, String patternStr) {
        if (mainStr == null || patternStr == null) {
            return -1;
        }

        int m = mainStr.length();
        int n = patternStr.length();
        if (n > m) {
            return -1;
        }

        int[] hashCodes = new int[m - n + 1];
        hashCodes[0] = calFirstSubStrHashCode(mainStr.substring(0, n));
        for (int i = 0; i < m - n + 1; i++) {
            hashCodes[i] = calHashCode(mainStr, i, hashCodes, n);
        }

        int patternHashCode =  calFirstSubStrHashCode(patternStr);
        for (int i = 0; i < m - n + 1; i++) {
            if (hashCodes[i] == patternHashCode) {
                return i;
            }
        }

        return -1;
    }

    private int calHashCode(String mainStr, int i, int[] hashCodes, int n) {
        return hashCodes[i - 1] - (mainStr.charAt(i - 1) - 'a')
                + (mainStr.charAt(i + n - 1) - 'a');
    }

    // abc => 0 + 1 + 2 = 3
    private int calFirstSubStrHashCode(String str) { // O(n)
        int n = str.length();

        int hashCode = 0;
        for (int i = 0; i < n; i++) {
            hashCode += (str.charAt(n - i - 1) - 'a');
        }

        return hashCode;
    }

    public static void main(String[] args) {
        System.out.println(new RK().indexOf("abcerfscsrx", "scs"));
    }
}
